import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class BinarySearchTree {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root = null;
    //查找
    public boolean find( int key){
        if(root == null){
            return false;
        }
        TreeNode cur = root;
        while (cur!=null){
            if(cur.val<key){
                cur =cur.right;
            } else if (cur.val>key) {
                cur =cur.left;
            }else {
                return true;
            }
        }
        return false;
    }

    //插入
    public boolean insert( int key){
        TreeNode node = new TreeNode(key);
        if(root == null){
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode parents =cur;
        while (cur!=null){
         if (key>cur.val){
             parents =cur;
               cur =cur.right;
            }else if (key<cur.val){
             parents =cur;
                cur =cur.left;
            }else {
             return false;
         }


        }

        if(parents.val<key){
            parents.right =node;
        }else {
            parents.left =node;
        }
        return true;

    }


}
